const { ListToNode, NodeToList, ListNode, timeL } = require("../utils.js");
/**
 * @param {number} n
 * @return {string[][]}
 */
var solveNQueens = function (n) {
  let res = [];
  const fun = (arr = []) => {
    if (arr.length === n) res.push(arr);
    else {
      let map = {};
      for (let i = 0; i < arr.length; i++) {
        map[arr[i]] = true;
        map[arr.length + arr[i] - i] = true;
        map[arr[i] + i - arr.length] = true;
      }
      for (let i = 0; i < n; i++) {
        if (!map[i]) {
          fun([...arr, i]);
        }
      }
    }
  };
  fun();
  res = res.map((item) => {
    return item.map((item) => {
      let str = "";
      for (let i = 0; i < n; i++) {
        str += item === i ? "Q" : ".";
      }
      return str;
    });
  });
  return res;
};
let n = 9;

timeL(solveNQueens, [n]);
